package com.example.lcpractice.sort_algorithm;

import java.util.Arrays;
import java.util.Random;

/**
 *
 * 快速排序的核心思想是分治：
 * 1. 选择数组中某个数作为基数，
 * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，
 * 2. 然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。
 * <a>https://juejin.cn/post/6844903910772047886</a>
 * @author hd
 * @date 2022-07-25 19:19
 * @description
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] a = new int[10];
        boolean flag = true;
        for (int i = 0; i < a.length; i++) {
            Random random = new Random();
            a[i] = random.nextInt(10);
        }
        System.out.println("随机数组：");
        System.out.println(Arrays.toString(a));
        System.out.println();

        quickSort(a, 0, a.length - 1);
        System.out.println();
        System.out.println("快排后：");
        System.out.println(Arrays.toString(a));

    }


    /**
     * 以第一个数字6作为基数，使用双指针i,j进行双向遍历：
     *
     *
     * 1、i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
     *
     *
     * 2、找到后将两个数字进行交换。继续循环交换直到<b>i>=j</b>结束循环；
     *
     *
     * 3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；
     * <p></p>
     * 作者：Java数据结构与算法
     * 链接：https://juejin.cn/post/6844903910772047886
     * 来源：稀土掘金
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param n
     * @param l
     * @param r
     */
    public static void quickSort(int n[], int l, int r) {
        if (l < r) {
            // 一趟快排，并返回交换后基数的下标
            // 交换后，此小值固定，index-1作为左区间上限
            // 交换后，此小值固定，index+1作为右边区间下限
            int index = patition(n, l, r);
            // 递归排序基数左边的数组
            quickSort(n, l, index - 1);
            // 递归排序基数右边的数组
            quickSort(n, index + 1, r);
        }

    }

    /**
     * 第一次只交换一对数字
     * 交换后返回小值的index
     * @param n
     * @param l
     * @param r
     * @return
     */
    public static int patition(int n[], int l, int r) {
        // p为基数，即待排序数组的第一个数
        int p = n[l];
        int i = l;
        int j = r;
        while (i < j) {
            // 从右往左找第一个小于基数的数
            while (n[j] >= p && i < j) {
                j--;
            }
            // 从左往右找第一个大于基数的数
            while (n[i] <= p && i < j) {
                i++;
            }
            // 找到后交换两个数
            swap(n, i, j);
        }
        // 使划分好的数分布在基数两侧
        swap(n, l, i);
        return i;
    }

    private static void swap(int n[], int i, int j) {
        int temp = n[i];
        n[i] = n[j];
        n[j] = temp;
    }
}

